/*
思路：
 对二叉树分情况：
 1. 如果二叉树采用孩子双亲表示法链接，求两个节点的最近公共祖先，实际就转化为两个链表相交求交点
 2. 如果二叉树是二叉搜索树：
       a. 如果树是空，直接返回null，没有最近公共祖先节点
       b. 如果两个节点中有一个是根节点，最近公共祖先一定是根节点
       c. 如果两个节点一个比根节点大，一个比根节点小，最近公共祖先一定是根节点
       d. 如果两个节点都比根节点小，递归到根的左子树中查找
       e. 如果两个节点都比根节点大，递归到根的右子树中查找

  3. 如果是普通的二叉树
     方法一：写一个判断节点是否在二叉树中的方法，可以参考类似二叉搜索树的方法解觉
             如果树是空，直接返回null，没有最近公共祖先节点
             如果两个节点中有一个是根节点，最近公共祖先一定是根节点
             如果两个节点一个在根节点的左子树，一个在根节点的右子树，最近公共祖先一定是根节点
             如果两个节点都在左子树中，递归到左子树中找
             如果两个节点都在右子树中，递归到右子树中找
     方法二：受孩子双亲表示法启发，如果能够知道节点到根的路径，问题就解决了
       获取节点pNode的路径，因为公共祖先从下往上找，因此将路径中的节点保存在栈中
        1. 如果是空树，直接返回
        2. 将根节点入栈，如果根节点和pNode是同一个节点，该节点到根的路径找到，否则：
        3. 递归在根节点的左子树中查找，如果找到，返回
        4. 如果在根节点的左子树中未找到，递归到根节点的右子树中找
        5. 如果右子树中没有找到，说明root一定不再路径中

        获取最近公共祖先：
         1. 在二叉树中获取两个节点的路径
         2. 如果两个路径中节点个数不一样，节点多的出栈，直到两个栈中元素相等
             相等时：再比较两个栈顶是不是同一个节点，如果是，最近公共祖先找到，
                     如果不是，两个栈同时进行出栈，继续比较，直到找到为止
*/
class Solution2 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(null == root){
            return null;
        }
        // p和q只有要一个在根节点的位置，则最近公共祖先就是根节点
        if(root == p || root == q){
            return root;
        }
        boolean ispInLeft = false;
        boolean ispInRight = false;
        boolean isqInLeft = false;
        boolean isqInRight = false;
        // 检测p是否在root的左子树中
        if(isNodeInTree(root.left, p)){
            ispInLeft = true;
            ispInRight = false;
        }
        else{
            ispInLeft = false;
            ispInRight = true;
        }
        if(isNodeInTree(root.left, q)){
            isqInLeft = true;
            isqInRight = false;
        }
        else{
            isqInLeft = false;
            isqInRight = true;
        }
        if(ispInLeft && isqInLeft){
            return lowestCommonAncestor(root.left, p, q);
        }
        else if(ispInRight && isqInRight){
            return lowestCommonAncestor(root.right, p, q);
        }
        else{
            return root;
        }
    }
    // 获取从root到node节点之间的路径，保存在sPath中
    private boolean isNodeInTree(TreeNode root, TreeNode node){
        if(null == root || null == node){
            return false;
        }
        // 如果root和node相等，说明root已经在树中了
        if(root == node){
            return true;
        }
        // 检测node是否在root的左子树中, 如果在就不用到右子树中检测
        return isNodeInTree(root.left, node) ||
                isNodeInTree(root.right, node);
    }
}
